<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<!-- NewPage -->
<html lang="en">
<head>
<title>GrammarAmbiguity</title>
<link rel="stylesheet" type="text/css" href="../../stylesheet.css" title="Style">
</head>
<body>
<script type="text/javascript"><!--
    if (location.href.indexOf('is-external=true') == -1) {
        parent.document.title="GrammarAmbiguity";
    }
//-->
</script>
<noscript>
<div>JavaScript is disabled on your browser.</div>
</noscript>
<!-- ========= START OF TOP NAVBAR ======= -->
<div class="topNav"><a name="navbar_top">
<!--   -->
</a><a href="#skip-navbar_top" title="Skip navigation links"></a><a name="navbar_top_firstrow">
<!--   -->
</a>
<ul class="navList" title="Navigation">
<li><a href="../../overview-summary.html">Overview</a></li>
<li><a href="package-summary.html">Package</a></li>
<li class="navBarCell1Rev">Class</li>
<li><a href="package-tree.html">Tree</a></li>
<li><a href="../../deprecated-list.html">Deprecated</a></li>
<li><a href="../../index-all.html">Index</a></li>
<li><a href="../../help-doc.html">Help</a></li>
</ul>
</div>
<div class="subNav">
<ul class="navList">
<li><a href="../../mmj/verify/Grammar.html" title="class in mmj.verify"><span class="strong">Prev Class</span></a></li>
<li><a href="../../mmj/verify/GrammarConstants.html" title="class in mmj.verify"><span class="strong">Next Class</span></a></li>
</ul>
<ul class="navList">
<li><a href="../../index.html?mmj/verify/GrammarAmbiguity.html" target="_top">Frames</a></li>
<li><a href="GrammarAmbiguity.html" target="_top">No Frames</a></li>
</ul>
<ul class="navList" id="allclasses_navbar_top">
<li><a href="../../allclasses-noframe.html">All Classes</a></li>
</ul>
<div>
<script type="text/javascript"><!--
  allClassesLink = document.getElementById("allclasses_navbar_top");
  if(window==top) {
    allClassesLink.style.display = "block";
  }
  else {
    allClassesLink.style.display = "none";
  }
  //-->
</script>
</div>
<div>
<ul class="subNavList">
<li>Summary:&nbsp;</li>
<li>Nested&nbsp;|&nbsp;</li>
<li>Field&nbsp;|&nbsp;</li>
<li><a href="#constructor_summary">Constr</a>&nbsp;|&nbsp;</li>
<li><a href="#method_summary">Method</a></li>
</ul>
<ul class="subNavList">
<li>Detail:&nbsp;</li>
<li>Field&nbsp;|&nbsp;</li>
<li><a href="#constructor_detail">Constr</a>&nbsp;|&nbsp;</li>
<li><a href="#method_detail">Method</a></li>
</ul>
</div>
<a name="skip-navbar_top">
<!--   -->
</a></div>
<!-- ========= END OF TOP NAVBAR ========= -->
<!-- ======== START OF CLASS DATA ======== -->
<div class="header">
<div class="subTitle">mmj.verify</div>
<h2 title="Class GrammarAmbiguity" class="title">Class GrammarAmbiguity</h2>
</div>
<div class="contentContainer">
<ul class="inheritance">
<li>java.lang.Object</li>
<li>
<ul class="inheritance">
<li>mmj.verify.GrammarAmbiguity</li>
</ul>
</li>
</ul>
<div class="description">
<ul class="blockList">
<li class="blockList">
<hr>
<br>
<pre>public class <span class="strong">GrammarAmbiguity</span>
extends java.lang.Object</pre>
<div class="block">GrammarAmbiguity was separated out from Grammar because a) Grammar was
 already getting too long, and b) the topic of "ambiguity" is large and the
 code will likely be a work-in-progress (until someone has a brainstorm).
 <p>
 At present, there are two levels of Grammar Ambiguity validation: basic and
 complete (aka "full"). The distinction between the two levels is somewhat
 arbitrary, but has to do with speed: a user does not need to validate her
 grammar every time the program is run. So "basic" is just the basics: are any
 grammar rules parseable using other grammar rules? The "complete" ambiguity
 checking process for a grammar may well prove to be quite time-consuming,
 involving many heuristics and passes through the grammar!
 <p>
 As of August, 2005, the "complete" level is stubbed out, except for a couple
 of little things. It will be a high priority project in the near future.</div>
<dl><dt><span class="strong">See Also:</span></dt><dd><a href="../../ConsolidatedListOfGrammarValidations.html">
      ConsolidatedListOfGrammarValidations.html</a>, 
<a href="../../BasicsOfSyntaxAxiomsAndTypes.html">
      BasicsOfSyntaxAxiomsAndTypes.html</a>, 
<a href="../../EssentialAmbiguityExamples.html">
      EssentialAmbiguityExamples.html</a>, 
<a href="../../CreatingGrammarRulesFromSyntaxAxioms.html">
      CreatingGrammarRulesFromSyntaxAxioms.html</a>, 
<a href="../../MetamathERNotes.html"> Nomenclature and
      Entity-Relationship Notes</a></dd></dl>
</li>
</ul>
</div>
<div class="summary">
<ul class="blockList">
<li class="blockList">
<!-- ======== CONSTRUCTOR SUMMARY ======== -->
<ul class="blockList">
<li class="blockList"><a name="constructor_summary">
<!--   -->
</a>
<h3>Constructor Summary</h3>
<table class="overviewSummary" border="0" cellpadding="3" cellspacing="0" summary="Constructor Summary table, listing constructors, and an explanation">
<caption><span>Constructors</span><span class="tabEnd">&nbsp;</span></caption>
<tr>
<th class="colOne" scope="col">Constructor and Description</th>
</tr>
<tr class="altColor">
<td class="colOne"><code><strong><a href="../../mmj/verify/GrammarAmbiguity.html#GrammarAmbiguity(mmj.verify.Grammar, boolean)">GrammarAmbiguity</a></strong>(<a href="../../mmj/verify/Grammar.html" title="class in mmj.verify">Grammar</a>&nbsp;grammar,
                boolean&nbsp;doCompleteGrammarAmbiguityEdits)</code>&nbsp;</td>
</tr>
</table>
</li>
</ul>
<!-- ========== METHOD SUMMARY =========== -->
<ul class="blockList">
<li class="blockList"><a name="method_summary">
<!--   -->
</a>
<h3>Method Summary</h3>
<table class="overviewSummary" border="0" cellpadding="3" cellspacing="0" summary="Method Summary table, listing methods, and an explanation">
<caption><span>Methods</span><span class="tabEnd">&nbsp;</span></caption>
<tr>
<th class="colFirst" scope="col">Modifier and Type</th>
<th class="colLast" scope="col">Method and Description</th>
</tr>
<tr class="altColor">
<td class="colFirst"><code>boolean</code></td>
<td class="colLast"><code><strong><a href="../../mmj/verify/GrammarAmbiguity.html#basicAmbiguityEdits()">basicAmbiguityEdits</a></strong>()</code>
<div class="block">The Primary Objective of basicAmbiguityEdits is to make a pass through
 Grammar's NotationRule Set and attempt to parse each Notation Grammar
 Rule using a Max Sequence number of Integer(dot)MAX_VALUE to absolutely
 positively confirm that none of the NotationRules is parseable using
 other NotationRules.</div>
</td>
</tr>
<tr class="rowColor">
<td class="colFirst"><code>boolean</code></td>
<td class="colLast"><code><strong><a href="../../mmj/verify/GrammarAmbiguity.html#fullAmbiguityEdits()">fullAmbiguityEdits</a></strong>()</code>
<div class="block">Right now this has just two edits, a warning about undefined
 non-terminals and an informational message that a grammar like peano.mm
 is unambiguous because every NotationRule is a "gimme match".</div>
</td>
</tr>
</table>
<ul class="blockList">
<li class="blockList"><a name="methods_inherited_from_class_java.lang.Object">
<!--   -->
</a>
<h3>Methods inherited from class&nbsp;java.lang.Object</h3>
<code>clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait</code></li>
</ul>
</li>
</ul>
</li>
</ul>
</div>
<div class="details">
<ul class="blockList">
<li class="blockList">
<!-- ========= CONSTRUCTOR DETAIL ======== -->
<ul class="blockList">
<li class="blockList"><a name="constructor_detail">
<!--   -->
</a>
<h3>Constructor Detail</h3>
<a name="GrammarAmbiguity(mmj.verify.Grammar, boolean)">
<!--   -->
</a>
<ul class="blockListLast">
<li class="blockList">
<h4>GrammarAmbiguity</h4>
<pre>public&nbsp;GrammarAmbiguity(<a href="../../mmj/verify/Grammar.html" title="class in mmj.verify">Grammar</a>&nbsp;grammar,
                boolean&nbsp;doCompleteGrammarAmbiguityEdits)</pre>
</li>
</ul>
</li>
</ul>
<!-- ============ METHOD DETAIL ========== -->
<ul class="blockList">
<li class="blockList"><a name="method_detail">
<!--   -->
</a>
<h3>Method Detail</h3>
<a name="fullAmbiguityEdits()">
<!--   -->
</a>
<ul class="blockList">
<li class="blockList">
<h4>fullAmbiguityEdits</h4>
<pre>public&nbsp;boolean&nbsp;fullAmbiguityEdits()</pre>
<div class="block">Right now this has just two edits, a warning about undefined
 non-terminals and an informational message that a grammar like peano.mm
 is unambiguous because every NotationRule is a "gimme match".</div>
<dl><dt><span class="strong">Returns:</span></dt><dd>false if errors found, true is no errors found.</dd></dl>
</li>
</ul>
<a name="basicAmbiguityEdits()">
<!--   -->
</a>
<ul class="blockListLast">
<li class="blockList">
<h4>basicAmbiguityEdits</h4>
<pre>public&nbsp;boolean&nbsp;basicAmbiguityEdits()</pre>
<div class="block">The Primary Objective of basicAmbiguityEdits is to make a pass through
 Grammar's NotationRule Set and attempt to parse each Notation Grammar
 Rule using a Max Sequence number of Integer(dot)MAX_VALUE to absolutely
 positively confirm that none of the NotationRules is parseable using
 other NotationRules.
 <p>
 During the initial pass through Grammar's NotationRule Set, useful
 information related to the rules is collected for subsequent use in
 ambiguity checking. This information is quite interesting and goes to the
 heart of the question of what makes a grammar (un)ambiguous -- embedding
 and overlapping notation rules (there are also deep mysteries to be
 pursued involving all-constant Notation Axioms which can embody
 characteristics of both constant "literals" and grammatical types, but
 those are not dealt with here.)
 <p>
 Secondary Objective: set each NotationRule.isGimmeMatchNbr to -1 if rule
 is *not* a "gimme match" or +1 if it is (zero indicates that the question
 has not yet been decided.) HOWEVER, there must be no intrinsic ambiguity
 in the rules themselves -- meaning that no grammar rule can be parsed
 using other grammar rules (and no duplicates.)
 <p>
 Tertiary Objective: if doCompleteGrammarAmbiguityEdits is set to true
 then intermediate results from this routine should be stored and made
 available to fullEdits(). Specifically, the non-gimme match Notation
 Rules will require deep investigations of their potential ambiguity and
 it is desireable that these results from this routine not be wasted:
 <p>
 <ul>
 <li>Notation Rules that "overlap"
 <li>Notation Rules with "embedding".
 </ul>
 <p>
 (these are not mutually exclusive since Rule A may be very short and be
 repeated more than once in Rule B.)
 <p>
 <b>Overlap</b>:
 <p>
 <ul>
 <li>a suffix portion of a rule matches the prefix portion of another
 rule, possibly itself.
 <li>At an extreme, suffix overlap with prefix would mean embedding (all
 of rule A overlaps rule B), so we make the definition that Overlap means
 that "suffix" and "prefix" overlap less than the entire rule.
 </ul>
 <p>
 <b>Embedding</b>:
 <p>
 <ul>
 <li>An entire rule is contained within another rule. This is *not*
 necessarily an error and may not be ambiguous; recall that before getting
 to this routine the Rules have already been validated -- they are not
 duplicates and cannot be parsed into other rules.
 <li>At an extreme the embedded Rule, A, may not be surrounded by symbols
 from Rule B; thus, A matches a prefix of B or A matches a suffix of B.
 This is called "recursion", either "left recursion" or "right recursion",
 respectively. But, as we shall see, recursion precludes a rule from being
 a "gimme", so we shall define recursion to be just a form of Embedding
 (there are grammatical parsing implications of recursion, but for now we
 will treat Embedding and Recursion as the same thing.)
 </ul>
 <p>
 <b>On Recursion</b>:
 <p>
 <ul>
 <li>an entire rule matches the prefix of another rule -- left recursion
 -- or the suffix of another rule -- right recursion.
 </ul>
 <p>
 <b>More on Gimme Matches</b>:
 <p>
 For the purposes of identifying a gimme we need to show that a rule has
 no overlaps and is neither embedded in nor contains an embedded rule, and
 is not recursive. We already know that it is not a duplicate rule and
 cannot itself be grammatically parsed into other rules.)
 <p>
 <b>More on Recursion -- cannot be Gimme Matches!</b>:
 <p>
 The fact that a rule is recursive DOES mean that it is *not* a gimme
 match. For example, if we have rules #1: A -> AB and #2: A -> ABB, then
 #2 is already in error because it is parseable (into #1(#1(a, b), b)))!
 Or consider these other examples:
 <p>
 <ul>
 <li><code>#1: A -&gt; (A) and #2: A -&gt; (A)B .... = not gimmes!</code>
 <li><code>#2: A -&gt; A * and #2: A -&gt; A * B ... = not gimmes!</code>
 <li><code>#3: A -&gt; * A and #2: A -&gt; * A B ... = not gimmes!</code>
 <li><code>#4: A -&gt; * A and #2: A -&gt; * * A ... = error!</code>
 <li><code>#5: A -&gt; * A and #2: A -&gt; + * A ... = not gimmes!</code>
 </ul>
 <p>
 So these *direct* recursion rules are either ambiguous or errors, but
 theye are *not* gimme matches in any case.
 <p>
 Note: *Indirect* recursions are possible. For example:
 <p>
 <ul>
 <code>
 <li><code>#1: E -&gt; A *</code>
 <li><code>#2: A -&gt; E * B</code>
 </ul>
 <p>
 which, depending on the set of other rules could mean both #1 and #2 are
 "gimme" matches. If there is Type Conversion <code>#3: E -&gt; A</code> then #1
 would turn out to be a non-gimme because a variant of #2 would have been
 generated, <code>#2.1: A -&gt; A * B</code>.</div>
<dl><dt><span class="strong">Returns:</span></dt><dd>false if errors found, true is no errors found.</dd></dl>
</li>
</ul>
</li>
</ul>
</li>
</ul>
</div>
</div>
<!-- ========= END OF CLASS DATA ========= -->
<!-- ======= START OF BOTTOM NAVBAR ====== -->
<div class="bottomNav"><a name="navbar_bottom">
<!--   -->
</a><a href="#skip-navbar_bottom" title="Skip navigation links"></a><a name="navbar_bottom_firstrow">
<!--   -->
</a>
<ul class="navList" title="Navigation">
<li><a href="../../overview-summary.html">Overview</a></li>
<li><a href="package-summary.html">Package</a></li>
<li class="navBarCell1Rev">Class</li>
<li><a href="package-tree.html">Tree</a></li>
<li><a href="../../deprecated-list.html">Deprecated</a></li>
<li><a href="../../index-all.html">Index</a></li>
<li><a href="../../help-doc.html">Help</a></li>
</ul>
</div>
<div class="subNav">
<ul class="navList">
<li><a href="../../mmj/verify/Grammar.html" title="class in mmj.verify"><span class="strong">Prev Class</span></a></li>
<li><a href="../../mmj/verify/GrammarConstants.html" title="class in mmj.verify"><span class="strong">Next Class</span></a></li>
</ul>
<ul class="navList">
<li><a href="../../index.html?mmj/verify/GrammarAmbiguity.html" target="_top">Frames</a></li>
<li><a href="GrammarAmbiguity.html" target="_top">No Frames</a></li>
</ul>
<ul class="navList" id="allclasses_navbar_bottom">
<li><a href="../../allclasses-noframe.html">All Classes</a></li>
</ul>
<div>
<script type="text/javascript"><!--
  allClassesLink = document.getElementById("allclasses_navbar_bottom");
  if(window==top) {
    allClassesLink.style.display = "block";
  }
  else {
    allClassesLink.style.display = "none";
  }
  //-->
</script>
</div>
<div>
<ul class="subNavList">
<li>Summary:&nbsp;</li>
<li>Nested&nbsp;|&nbsp;</li>
<li>Field&nbsp;|&nbsp;</li>
<li><a href="#constructor_summary">Constr</a>&nbsp;|&nbsp;</li>
<li><a href="#method_summary">Method</a></li>
</ul>
<ul class="subNavList">
<li>Detail:&nbsp;</li>
<li>Field&nbsp;|&nbsp;</li>
<li><a href="#constructor_detail">Constr</a>&nbsp;|&nbsp;</li>
<li><a href="#method_detail">Method</a></li>
</ul>
</div>
<a name="skip-navbar_bottom">
<!--   -->
</a></div>
<!-- ======== END OF BOTTOM NAVBAR ======= -->
</body>
</html>
